#include <stdio.h>
#include <malloc.h>
#include <time.h>
#define MAXSIZE 3
#define ZERO 0
#define TRUE 1
#define FALSE 0
#define EqualFun equal
#define SetValue setvalue
typedef int STATUS;
typedef int NODETYPE[MAXSIZE][MAXSIZE];
typedef struct 
{
    NODETYPE node;
    float evaluate;
    double step;
}NODE;
typedef struct Neighbor
{
    NODE node;
    struct Neighbor *next;
}*NEIGHBOR, *PATH;
typedef struct Paths
{
    PATH path;
    struct Paths *next;
}*STACK, *PATHS;


int Equal(NODE *n1, NODE *n2, int (*fun)()) 
{
    return (int)fun(n1, n2);
}

void Set(NODE *node1, NODE *node2, void (*fun)())
{
    fun(node1, node2);
}

void setvalue(NODE *node1, NODE *node2)
{                                                   // 节点(矩阵)赋值
    int i, j;                                       // 行下标和列下标
    for ( i = 0; i < MAXSIZE; i++)                  // 行下标
        for ( j = 0;j < MAXSIZE; j++)               // 列下标
            node1->node[i][j] = node2->node[i][j];  // 对数组元素赋值
    node1->evaluate = node2->evaluate;              // 启发信息
    node1->evaluate = node2->evaluate;
    node1->step = node2->step;    
}

float Evaluate(NODE *node1, NODE *node2)
{                                                           // 两个状态中不同数字的个数
    int i, j;                                               // 行下标和列下标
    float res = 0;                                          // 数字不同的个数
    for ( i = 0; i < MAXSIZE; i++)                          // 行下标
        for ( j = 0; j < MAXSIZE; j++)                      // 列下标
            if(node1->node[i][j] != node2->node[i][j])
                res++;                                      // 累加不同数字的个数
    return res;                                             // 返回数字不同的个数
}

void EvaluateAdjacents(NEIGHBOR adjacents, NODE *node, NODE *end)
{                                                           // 根据当前状态和状态评估所有状态
    NEIGHBOR br = adjacents;
    while (br)                                              // 评估所有状态
    {
        br->node.evaluate = Evaluate(&(br->node), end);     // 与目标状态的差异
        br->node.step = node->step + 1;                     // 在当前状态深度加深
        br = br->next;
    }
}

NEIGHBOR CopyAdjacents(NEIGHBOR adjacents)
{				//节点集复制 
    NEIGHBOR copynode, lastnode, head = NULL;			//没有子节点 
    while (adjacents)
    {
        copynode = (NEIGHBOR)malloc(sizeof(struct Neighbor));
        Set(&(copynode->node), &(adjacents->node), setvalue);//复制节点 
        copynode->next = NULL;
        if(head == NULL) head = copynode;//第一个节点 
        else									//建立链接，复制子节点集 
            lastnode->next = copynode;
        lastnode = copynode;
        adjacents = adjacents -> next; 				//下一个节点 
    }
    return head;									//返回头节点指针 
}

PATH CopyPath(PATH path)
{// 复制路径
    PATH tempath;
    tempath = (PATH)CopyAdjacents((NEIGHBOR)path);    //路径与兄弟节点集合相同
    return tempath;
}

STACK PopANode_Heuristic_by_Mini(STACK stack, NODE *node, PATH *path)
{
    STACK p = stack, p1 = NULL, p2, p3;
    PATH tempath;
    double ev = 1e100;
    if(p == NULL) return stack;
    *path = NULL;
    while(p != NULL)
    {
        tempath = p->path;
        if(tempath->node.evaluate + tempath->node.step < ev)
        {
            ev = tempath->node.evaluate + tempath->node.step;
            p2 = p1;
            p3 = p;
        }
        p1 = p;
        p = p->next;
    }
    tempath = p3->path;
    Set(node, &(tempath->node), setvalue);
    *path = CopyPath(tempath);
    if(p3 == stack)
        stack = p3 -> next;
    else
        p2->next = p3->next;
    free(p3);
    return stack;
}

PATH AddANodeToPath(NODE *node, PATH path)
{//节点加入路径中
    PATH p;
    p = (NEIGHBOR)malloc(sizeof(struct Neighbor)); //开辟节点空间
    Set(&(p->node), node, setvalue);                    //赋值
    if(path == NULL)                                 //路径上第一个节点
        p->next = NULL;
    else
        p->next = path;                             //加入到路径头部
    path = p;                                       //路径倒序加入
    return path;                                    //返回路径头部
}

STACK PushAPath(STACK stack, PATH path)
{// 一条路径进栈
    PATH tempath;
    STACK st;
    tempath = CopyPath(path);                           // 复制路径
    st = (PATHS)malloc(sizeof(struct Paths));           // 路径节点
    st->path = tempath;                                 // 置路径于栈中
    if (stack == NULL)                                  // 第 1 条路径
        st->next = NULL;
    else                                                // 已有路径
        st->next = stack;
    stack = st;
    return stack;
}

NEIGHBOR ClearAdjacents(NEIGHBOR nb)	
{//回收图节点空间 
    NEIGHBOR nb1 = nb;				//临时节点变量 
    while (nb)
    {
        nb1 = nb;
        nb = nb->next;
        free(nb1);					//回收单元 
    }
    return nb;						//返回NULL 
}

PATH ClearPath(PATH path)
{// 回收路径空间
    path = (PATH)ClearAdjacents((NEIGHBOR)path); // 路径与兄弟节点集合形式相同
    return path;
}

STATUS equal(NODE *node1, NODE *node2)        // 判断节点(矩阵)是否相同
{
    int i, j;                               // 二维数组的行下标和列下标
    STATUS flag = FALSE;                     // 二维数组对应的元素相等, 九宫格相同
    for(i = 0;i < MAXSIZE; i++)             // 行下标变化
    {                          
        for(j = 0;j < MAXSIZE; j++)         // 列下标变化
            if(node1->node[i][j] != node2->node[i][j])  // 其中有一个元素不相等
            {      
                flag = TRUE;               // 不相等
                break;                      // 结束
            }
        if(flag == TRUE) break;            // 九宫格不相同
    }
    return flag;
}

STATUS Locate(NODE *node, int *hori, int *vert, int zero)   
    /* horizon(水平),verticality(垂直) */        
{                                           // 由节点获取所有子节点
    int i, j;                               // 二维数组的行下标和列下标
    STATUS flag = FALSE;
    for(i = 0; i < MAXSIZE; i++)            // 行下标
    {
        for(j = 0; j < MAXSIZE; j++)        // 列下标
            if(node->node[i][j] == zero)    // zero表示空格
            {
                *hori = i;                  // 空格所在的行和列
                *vert = j;
                flag = TRUE;                // 找到空格, 结束
                break;
            }
        if(flag == TRUE) break;
    }
    return flag;                            // 是否找到空格
}

void Exchange(NODE *node, int hori1, int vert1, int hori2, int vert2)
{                   // 位置 [hori1, vert1] 的元素与位置 [hori2, vert2] 的元素交换位置
    int tempnode;
    tempnode = node->node[hori1][vert1];
    node->node[hori1][vert1] = node->node[hori2][vert2];// 交换九宫格的数字
    node->node[hori2][vert2] = tempnode;
}

NEIGHBOR AddAnAdjacents(NEIGHBOR adjacents, NODE *node)
{// 收集新的节点
    NEIGHBOR n, pn;					//相邻节点变量 
    n = (NEIGHBOR)malloc(sizeof(struct Neighbor));	//动态开辟一个相邻单元 
    n->next = NULL;
    Set(&(n->node), node, SetValue);					//本例中与strcpy(b->node, node);等价 
    if (adjacents == NULL)							//没有相邻节点的情况 
        adjacents = n;
    else									//有相邻节点的情况 
    {
        pn = adjacents;
        while (pn -> next) pn = pn -> next;
        pn -> next = n;
    }
    return adjacents;								//返回相邻节点 
}  

NEIGHBOR ExpandNodes(NODE *node, int zero)   // 生成新的节点集合
{
    NEIGHBOR adjacents = NULL;              // 所有派生的节点集合
    int h, v;                               // 空格位置
    NODE *tempnode = (NODE *)malloc(sizeof(NODE));                          // 临时节点
    if(!Locate(node, &h, &v, zero))         // 没有找到空格位置,若找到
        return adjacents;                   // 则位置为h, v             
    if(h == 0&&v == 0)                      // 空格位置
    {
        Set(tempnode, node, SetValue);      // 对九宫格的节点赋值
        Exchange(tempnode, h, v, h + 1, v); // 交换位置
        adjacents = AddAnAdjacents(adjacents, tempnode);// 收集新的节点
        Set(tempnode, node, setvalue);
        Exchange(tempnode, h, v, h, v + 1);
        adjacents = AddAnAdjacents(adjacents, tempnode);
    }
    if(h == 0&&v == 1)                      // 空格位置
    {
        Set(tempnode, node, SetValue);      // 对九宫格的节点赋值
        Exchange(tempnode, h, v, h, v - 1); // 交换位置
        adjacents = AddAnAdjacents(adjacents, tempnode);// 收集新的节点
        Set(tempnode, node, setvalue);
        Exchange(tempnode, h, v, h, v + 1);
        adjacents = AddAnAdjacents(adjacents, tempnode);
        Set(tempnode, node, setvalue);
        Exchange(tempnode, h, v, h + 1, v);
        adjacents = AddAnAdjacents(adjacents, tempnode);
    }
    if(h == 0&&v == 2)                      // 空格位置
    {
        Set(tempnode, node, SetValue);      // 对九宫格的节点赋值
        Exchange(tempnode, h, v, h, v - 1); // 交换位置
        adjacents = AddAnAdjacents(adjacents, tempnode);// 收集新的节点
        Set(tempnode, node, setvalue);
        Exchange(tempnode, h, v, h + 1, v);
        adjacents = AddAnAdjacents(adjacents, tempnode);
    }
    if(h == 1&&v == 0)                      // 空格位置
    {
        Set(tempnode, node, SetValue);      // 对九宫格的节点赋值
        Exchange(tempnode, h, v, h - 1, v); // 交换位置
        adjacents = AddAnAdjacents(adjacents, tempnode);// 收集新的节点
        Set(tempnode, node, setvalue);
        Exchange(tempnode, h, v, h + 1, v );
        adjacents = AddAnAdjacents(adjacents, tempnode);
        Set(tempnode, node, setvalue);
        Exchange(tempnode, h, v, h , v+ 1);
        adjacents = AddAnAdjacents(adjacents, tempnode);
    }
    if(h == 1&&v == 1)
    {
        Set(tempnode, node, SetValue);      // 对九宫格的节点赋值
        Exchange(tempnode, h, v, h - 1, v); // 交换位置
        adjacents = AddAnAdjacents(adjacents, tempnode);// 收集新的节点
        Set(tempnode, node, SetValue);      // 对九宫格的节点赋值
        Exchange(tempnode, h, v, h + 1, v); // 交换位置
        adjacents = AddAnAdjacents(adjacents, tempnode);// 收集新的节点 
        Set(tempnode, node, SetValue);      // 对九宫格的节点赋值
        Exchange(tempnode, h, v, h, v - 1); // 交换位置
        adjacents = AddAnAdjacents(adjacents, tempnode);// 收集新的节点
        Set(tempnode, node, SetValue);      // 对九宫格的节点赋值
        Exchange(tempnode, h, v, h, v + 1); // 交换位置
        adjacents = AddAnAdjacents(adjacents, tempnode);// 收集新的节点
    }
    if(h == 1&&v == 2)
    {
        Set(tempnode, node, SetValue);      // 对九宫格的节点赋值
        Exchange(tempnode, h, v, h - 1, v); // 交换位置
        adjacents = AddAnAdjacents(adjacents, tempnode);// 收集新的节点
        Set(tempnode, node, SetValue);      // 对九宫格的节点赋值
        Exchange(tempnode, h, v, h + 1, v); // 交换位置
        adjacents = AddAnAdjacents(adjacents, tempnode);// 收集新的节点
        Set(tempnode, node, SetValue);      // 对九宫格的节点赋值
        Exchange(tempnode, h, v, h, v - 1); // 交换位置
        adjacents = AddAnAdjacents(adjacents, tempnode);// 收集新的节点
    }
    if (h == 2&&v == 0)
    {
        Set(tempnode, node, SetValue);      // 对九宫格的节点赋值
        Exchange(tempnode, h, v, h - 1, v); // 交换位置
        adjacents = AddAnAdjacents(adjacents, tempnode);// 收集新的节点
        Set(tempnode, node, SetValue);      // 对九宫格的节点赋值
        Exchange(tempnode, h, v, h, v + 1); // 交换位置
        adjacents = AddAnAdjacents(adjacents, tempnode);// 收集新的节点
    }
    if (h == 2&&v == 1)
    {
        Set(tempnode, node, SetValue);      // 对九宫格的节点赋值
        Exchange(tempnode, h, v, h - 1, v); // 交换位置
        adjacents = AddAnAdjacents(adjacents, tempnode);// 收集新的节点
        Set(tempnode, node, SetValue);      // 对九宫格的节点赋值
        Exchange(tempnode, h, v, h, v - 1); // 交换位置
        adjacents = AddAnAdjacents(adjacents, tempnode);// 收集新的节点
        Set(tempnode, node, SetValue);      // 对九宫格的节点赋值
        Exchange(tempnode, h, v, h, v + 1); // 交换位置
        adjacents = AddAnAdjacents(adjacents, tempnode);// 收集新的节点
    }
    if (h == 2&&v == 2)
    {
        Set(tempnode, node, SetValue);      // 对九宫格的节点赋值
        Exchange(tempnode, h, v, h - 1, v); // 交换位置
        adjacents = AddAnAdjacents(adjacents, tempnode);// 收集新的节点
        Set(tempnode, node, SetValue);      // 对九宫格的节点赋值
        Exchange(tempnode, h, v, h, v - 1); // 交换位置
        adjacents = AddAnAdjacents(adjacents, tempnode);// 收集新的节点       
    }
    return adjacents;
}

PATHS AddAPathToPaths(PATH path, PATHS paths)
{//路径加入路径集合
    PATH copypath;
    PATHS ps = NULL, p;
    if(path == NULL) return paths;                  // 没有路径
    copypath = CopyPath(path);                      // 复制路径
    ps = (PATHS)malloc(sizeof(PATHS)); // 开辟路径集合节点
    ps->path = copypath;                               // 复制的路径置入
    ps->next = NULL;                                
    if (paths == NULL)                              // 路径集合为空
        paths = ps;                        
    else                                            // 新节点路径放置最后
    {
        p = paths;
        while(p->next) p = p->next;
        p->next = ps;
    }
    return paths;    
}

STATUS IsInPath(NODE *node, PATH path)			//节点在路径中 
{
	PATH p=path;
	STATUS flag=FALSE;
	while(p)									//节点是否在路径中的标识 
	{
		if(Equal(node, &(p->node), EqualFun)==0)	//node在路径中 
		{
			flag=TRUE;
			break;	
		}
		else
			p=p->next;
	}
	return flag;								//返回真、假值 
}

NEIGHBOR DeleteNodeInPath(NEIGHBOR adjacents, PATH path)
{									//从adjacents中删除节点在路径path中的节点 
	NEIGHBOR n1=adjacents, n2;		
	STATUS flag=FALSE;
	while(n1)							//节点集合的每个节点 
	{							
		flag=IsInPath(&(n1->node), path);	//节点是否在路径中 
		if(flag==TRUE)					//节点在路径中 
		{
			if(n1==adjacents)			//删除节点 
			{
				adjacents=n1->next;		//下一个节点 
				free(n1);				//删除当前节点 
				n1=adjacents;			//其他节点 
			}
			else						//删除节点 
			{
				n2->next=n1->next;		//NULL 
				free(n1);				//删除当前节点 
				n1=n2->next;			//NULL 
			}
		}
		else							//节点不在路径中 
		{
			n2=n1;						//下一个节点 
			n1=n1->next;
		}
	}
	return adjacents;
}

PATHS FormPathsFromNodes(NEIGHBOR adjacents, PATH path, PATHS paths)
{						//将不在路径中的节点加入路径，形成路径集合 
	PATH tempath;
	adjacents=DeleteNodeInPath(adjacents, path);			//删除构成回路的节点 
	while(adjacents)										//所有不构成回路的节点 
	{
		tempath=CopyPath(path);								//复制路径 
		tempath=AddANodeToPath(&(adjacents->node), tempath);	//路径中加入一个节点 
		paths=AddAPathToPaths(tempath, paths);				//新路径加入路径集合 
		adjacents=adjacents->next;							//下一个节点 
	}	
	return paths;											//下一个路径集合 
}

PATHS CopyPaths(PATHS paths)
{// 复制路径集合, 返回路径集合的指针
    PATHS copynode, lastnode, head = NULL;
    while (paths)                                       // 路径集合不为空
    {
        copynode = (PATHS) malloc(sizeof(struct Paths)); //路径节点
        copynode->path = CopyPath(paths->path);         // 复制一条路径
        copynode->next = NULL;                          // 复制路径
        if (head == NULL)                               // 第一条路径
            head = copynode;
        else                                            // 其他路径
            lastnode->next = copynode;
        lastnode = copynode;                            // 加入路径集合
        paths = paths->next;
    }
    return head;
}

STACK PushPaths(STACK stack, PATHS paths)
{// 所有路径进栈
    PATHS p, head;
    head = CopyPaths(paths);                // 复制路径集合
    p = head;
    if(p != NULL)                           // 逐一加入栈中
    {
        while(p->next) p = p->next;
        p->next = stack;
        stack = head;
    }
    return stack;
}

PATHS ClearPaths(PATHS paths)
{// 回收路径空间
    PATHS paths1 = paths;
    while(paths)                              // 所有路径
    {
        paths1 = paths;
        ClearPath(paths1->path);             //回收一条路径空间
        paths = paths->next;                 // 下一条路径
        free(paths1);
    }
    return paths;
}

STACK ClearStack(STACK stack)
{// 回收栈空间
    stack = ClearPaths((PATHS)stack);          //堆栈与路径集合的形式相同
    return stack;
}

void priNode(NODE *node)
{                       // 显示节点(矩阵)
    int i, j;                               // 二维数组的行下标和列下标
    for(i = 0; i < MAXSIZE; i++)            // 按行下标显示
    {
        for(j = 0; j < MAXSIZE; j++) 
            printf("%5d", node->node[i][j]); // 按列下标显示
        printf("\n");                       // 换行显示         
    }
    printf("Evaluate = %.2f\n", node->evaluate);
    printf("Step = %.lf\n", node->step);
    printf("***********************\n");
}

STATUS SearchPath(NODE *start, NODE *end, PATH *path, int zero)
{                                                                   // 判断节点是否在图中
    NODE node;                                                      // 节点
    NEIGHBOR adjacents;                                             // 相邻节点集合
    STACK stack = NULL;                                             // 线性空间
    STATUS flag = FALSE;                                            // 搜索是否成功(是否找到目标节点)
    PATH tempath = NULL;                                            // 临时路径
    PATHS paths = NULL;                                             // 生成新的路径集合
    start->step = 0;                                                // 设置初始搜索的深度
    start->evaluate = Evaluate(start, end);                         // 将不相等数字的方格数初始化
    tempath = AddANodeToPath(start, tempath);                       // 形成路径
    stack = PushAPath(stack, tempath);                              // 路径进栈
    while (stack)                                                   // 有路径存在
    {
        tempath = ClearPath(tempath);                               // 清空路径
        stack = PopANode_Heuristic_by_Mini(stack, &node, &tempath); // 最优节点
        if(Equal(end, &node, EqualFun) == FALSE)                     // 最优节点是否为目标节点
        {
            flag = TRUE;                                            // 最优节点是目标节点
            *path = CopyPath(tempath);                              // 获取路径
            break;                                                  // 退出求解
        }
        adjacents = ExpandNodes(&node, zero);                       // 搜索下一级所有节点
        EvaluateAdjacents(adjacents, &node, end);                   // 计算启发式信息的值
        paths = FormPathsFromNodes(adjacents, tempath, paths);      // 形成路径集合
        stack = PushPaths(stack, paths);                            // 所有新的路径进栈
        paths = ClearPaths(paths);                                  // 清空所有路径
    }
    ClearStack(stack);                                              // 清空堆栈
    return flag;
}

void RevPath(PATH path)
{// 路径倒序
    int num = 0, i;
    NODE *nodes;
    PATH p = path;
    while (p)                                       //统计路径节点的个数
    {
        p = p->next;num++;        
    }
    nodes = (NODE *)malloc(num*sizeof(NODE));       // 开辟一维数组
    for(i = 0,p = path;p;p = p->next, i++)          //读取路径节点置于数组中
        Set(&(nodes[i]), &(p->node), SetValue);           
    for(i = num - 1, p = path; p; p = p->next, i--)//数组数据倒序置于路径中
        Set(&(p->node), &(nodes[i]), SetValue);          
    free(nodes);                                   //回收数组空间
}

void priAdjacents(NEIGHBOR adjacent)
{
    while (adjacent)
    {
        priNode(&(adjacent->node));
        adjacent = adjacent->next;
    }
}

void priPath(PATH path)
{//显示路径
    priAdjacents((NEIGHBOR)path);                     // 路径与兄弟节点集合形式相同
}

int LenthOfPath(PATH path)
{
    int num = 0;
    while (path)                                       //统计路径节点的个数
    {
        path = path->next;num++;        
    }
    return num;
}


void main() 
{
    clock_t t1, t2;
    t1 = clock();
    STACK stack = NULL;                                             // 路径堆栈
    PATH path = NULL;                                               // 路径
    STATUS flag;                                                    // 是否搜索到路径的标识
    NODE start = {1, 2, 3, 8, 4, 5, 7, 0, 6, 0.0, 0},               // 初始状态
          end  = {1, 2, 3, 8, 0, 4, 7, 6, 5, 0.0, 0};               // 目标状态
    printf("Search fron:\n"); priNode(&start);                      // 显示初始状态  
    printf("to:\n"); priNode(&end);                                 // 显示目标状态
    flag = SearchPath(&start, &end, &path, ZERO);                   // 求解路径
    if(flag != 0) printf("Path=\n");                                // 显示路径
    RevPath(path);                                                      // 路径倒序
    priPath(path);                                                      // 显示路径
    printf("\nStep=%ld, Status = %d\n", LenthOfPath(path), flag);
    printf("\n***********************\n");
    ClearPath(path);                                                // 清空路径, 回收路径空间
    t2 = clock();
    printf("time=%fs\n", (double)(t2 - t1) / CLOCKS_PER_SEC);
}